using System;

// Largest prime factor
// Problem 3
// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143 ?

namespace CSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            var start = DateTime.Now;

            long number = 600851475143;
            
            for(var i = 2; i < number; i++)
            {
	            if(number % i == 0 && IsPrime(i))
	            {
		            number = number / i;		
	            }
            }

            Console.WriteLine(number);

            var end = DateTime.Now;
            var time = end - start;

            Console.WriteLine("Time: {0}", time);
        }

        public static bool IsPrime(long n)
        {
            if (n < 2)
            {
                return false;
            };

            if (n % 2 == 0)
            {
                return (n == 2);
            }

            var m = Math.Sqrt(n);

            for (var i = 3; i <= m; i += 2)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }

            return true;
        }
    }
}
